package DynamicProgrammingPackage;

/**
 * @author Lzm
 * @version 1.0
 */
public class uniquePathsWithObstacles_ {
  public static void main(String[] args) {
    int[][] o = new int[][]{{0,0,0},{0,1,0},{0,0,0}};
    System.out.println(uniquePathsWithObstacles(o));
  }

  // 1. dp[i][j]表示从(0,0)移动到(i,j)一共有dp[i][j]种路径
  // 2. 递推公式:
  // 2.1 dp[i][j]的上方无障碍且左方无障碍 dp[i][j] = dp[i - 1][j] + dp[i][j - 1]
  // 2.2 dp[i][j]的上方无障碍但左方有障碍 dp[i][j] = dp[i][j - 1]
  // 2.3 dp[i][j]的上方有障碍但左方无障碍 dp[i][j] = dp[i - 1][j]
  // 3. 初始化当ob[0][j] != 1 dp[0][j] = 1,ob[i][0] != 1dp[i][0] = 1; 如果有障碍的话那就走不到(0,j)和(i,0)
  // 4. 遍历顺序从左到右,从上到下
  public static int uniquePathsWithObstacles(int[][] obstacleGrid) {
    if (obstacleGrid[obstacleGrid.length - 1][obstacleGrid[0].length- 1] == 1){
      return 0;
    }
    if (obstacleGrid[0][0] == 1){
      return 0;
    }
    int[][] dp = new int[obstacleGrid.length][obstacleGrid[0].length];
    for (int i = 0 ; i < obstacleGrid.length && obstacleGrid[i][0] != 1; i++){
      dp[i][0] = 1;
    }
    for (int j = 0 ; j < obstacleGrid[0].length && obstacleGrid[0][j] != 1 ; j++){
      dp[0][j] = 1;
    }
    for (int i = 1 ; i < obstacleGrid.length ; i++){
      for (int j = 1 ; j < obstacleGrid[0].length ; j++){
        if (obstacleGrid[i - 1][j] != 1 && obstacleGrid[i][j - 1] != 1){
          dp[i][j] = dp[i - 1][j] + dp[i][j - 1];
          continue;
        }
        else if (obstacleGrid[i - 1][j] == 1 && obstacleGrid[i][j - 1] != 1){
          dp[i][j] = dp[i][j - 1];
          continue;
        }
        else if (obstacleGrid[i - 1][j] != 1 && obstacleGrid[i][j - 1] == 1){
          dp[i][j] = dp[i - 1][j];
          continue;
        }
      }
    }
    return dp[obstacleGrid.length - 1][obstacleGrid[0].length - 1];
  }
}
